package main

import (
	"fmt"
	"strconv"
	"strings"
)

const NodeEmpty = "#"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//路径和
func pathSum(root *TreeNode, sum int) [][]int {
	res := [][]int{}
	findPath(root, sum, &res, []int{})
	return res
}

//查询路径
/**
33行为什么不需要回退stack? 
stack是切片，在函数传递前后可能公用底层数组，但是其长度是各副本独享的
举个例子，s1是原切片，s2是函数传递后的切片
在函数内s2 = append(s2,xx)
假设s2在append后和s1不再共享底层数组，对回溯使用s1的计算无影响
假设s2在append后和s1继续共享底层数组,此时s1长度为l,s2长度为l+1，对回溯使用s1的计算无影响
 */
func findPath(root *TreeNode, sum int, res *[][]int, stack []int) {
	if root == nil {
		return
	}

	stack = append(stack, root.Val)
	if sum == root.Val && root.Left == nil && root.Right == nil {
		*res = append(*res, append([]int{}, stack...))
		//stack = stack[:len(stack)-1]	
		return
	}

	sum = sum - root.Val
	findPath(root.Left, sum, res, stack)
	findPath(root.Right, sum, res, stack)
}

//字符串转数字
func AtoI(s string) int {
	i, err := strconv.Atoi(s)
	if err != nil {
		panic(err)
	}
	return i
}

//生成二叉树
func generateTree(nums []string) *TreeNode {
	l := len(nums)
	if l == 0 {
		return nil
	}

	i := 0
	head := &TreeNode{Val: AtoI(nums[0])}
	q := []*TreeNode{}
	q = append(q, head)
	i++

	for len(q) != 0 && i < l {
		current := q[0]
		q = q[1:]

		if i < l {
			if nums[i] != NodeEmpty {
				current.Left = &TreeNode{Val: AtoI(nums[i])}
				q = append(q, current.Left)
			}
			i++
		}

		if i < l {
			if nums[i] != NodeEmpty {
				current.Right = &TreeNode{Val: AtoI(nums[i])}
				q = append(q, current.Right)
			}
			i++
		}
	}

	return head
}

func main() {
	a:=[]int{}
	a = append(a,1)
	a = append(a,1)
	a = append(a,1)
	a = append(a,1)
	a = append(a,1)
	a = append(a,1)
	var input, sum string
	fmt.Println("输入路径和: ")
	fmt.Scanln(&sum)
	fmt.Println("输入二叉树内容(#号表示空节点): ")
	fmt.Scanln(&input)
	strslice := strings.Split(input, ",")
	tree := generateTree(strslice)
	res := pathSum(tree, AtoI(sum))
	if len(res) > 0 {
		for _, v := range res {
			fmt.Println(v)
		}
	} else {
		fmt.Println("无满足条件的路径")
	}
}
